package com.tys.algorithm.advanced.code.class09;

import java.util.HashMap;

/**
 * 一种特殊的单链表节点类描述如下：
 * class Node{
 * int value;
 * Node next;
 * Node rand;
 * Node(int val){
 * value=val;
 * }
 * }
 * rand指针是单链表节点结构中的新增指针，rand可能指向链表中任意节点，也可能指向null
 * 给定一个由node节点类型组成的无环单链表的头节点head，实现一个函数完成这个链表的复制，返回复制的新链表的
 * 头节点
 * 要求：时间复杂度O(N),空间复杂度O(1)
 * <p>
 * 测试链接 : https://leetcode.com/problems/copy-list-with-random-pointer/
 */
public class Code04_CopyListWithRandom {

    public static class Node {
        int val;
        Node next; //下一个节点
        Node random; //指向链表中任意节点，也可能指向null

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    //方法1：使用HashMap
    public static Node copyRandomList1(Node head) {
        // key 老节点
        // value 新节点
        HashMap<Node, Node> map = new HashMap<Node, Node>();
        Node cur = head;
        //遍历链表生成克隆节点：拷贝所有的节点到HashMap
        while (cur != null) {
            //key=老节点, value=新节点
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        //这里是将新节点的next和rand进行指向，没有拷贝操作
        cur = head;
        while (cur != null) {
            // cur 老
            // map.get(cur) = 新节点
            // 新.next ->  cur.next克隆节点找到
            //根据老节点找新节点
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        //返回新头
        return map.get(head);
    }

    //方法2：不使用HashMap
    public static Node copyRandomList2(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Node next = null;
        //每个节点后面插入复制的新节点
        // 1 -> 2 -> 3 -> null
        // 1 -> 1' -> 2 -> 2' -> 3 -> 3'
        //cur=1
        while (cur != null) {
            //next=2
            next = cur.next;
            //cur.next=cur的拷贝=1`
            cur.next = new Node(cur.val);
            //1`的next是2
            cur.next.next = next;
            //cur跳2
            cur = next;
        }
        cur = head;
        Node copy = null;

        // 1 1' 2 2' 3 3'
        // 依次设置 1' 2' 3' random指针
        //cur=1
        while (cur != null) {
            //next=2
            next = cur.next.next;
            //copy=1`
            copy = cur.next;
            //设置1`的random指针：cur.random的下一个就是cur.random的拷贝
            copy.random = cur.random != null ? cur.random.next : null;
            cur = next;
        }
        Node res = head.next;
        cur = head;
        // 老 新 混在一起，next方向上，random正确
        // next方向上，把新老链表分离
        // 1 1' 2 2' 3 3'
        //cur=1
        while (cur != null) {
            //next=2
            next = cur.next.next;
            //copy=1`
            copy = cur.next;
            //1->2
            cur.next = next;
            //1` -> 2`
            copy.next = next != null ? next.next : null;
            //1 跳到 2
            cur = next;
        }
        return res;
    }

}
